Apple II
Technical Notes
_____________________________________________________________________________
                                                  Developer Technical Support


Pascal
#14:    Apple Pascal 1.3 TREESEARCH and IDSEARCH

Revised by:    Cheryl Ewy                                       November 1988
Written by:    Cheryl Ewy                                           June 1985

This Technical Note describes the TREESEARCH and IDSEARCH routines which were 
built into Pascal 1.2 and earlier, but which are separate entities for Pascal 
1.3.
_____________________________________________________________________________


Introduction

In Apple II Pascal versions 1.0 through 1.2, TREESEARCH and IDSEARCH were 
special-purpose built-in routines which could be called from within a Pascal 
program.  The routines existed primarily for use by the Compiler and Libmap 
but were also available for use by applications.  In Apple II Pascal 1.3, the 
routines were removed due to space requirements.  Since some applications use 
these routines, they are being supplied as 6502 codefiles which can be linked 
to Pascal programs.  To use the routines, the Pascal host program must declare 
them as EXTERNAL (see the following sections for details).  After compiling 
the host program, use the Linker to link the file TRS.CODE (TREESEARCH) or the 
file IDS.CODE (IDSEARCH).


The TREESEARCH Function

TREESEARCH is a fast assembly language function for searching a binary tree 
with a particular kind of structure.  The external declaration is:

    FUNCTION TREESEARCH (ROOTPTR : ^NODE;
                        VAR NODEPTR : ^NODE;
                        NAMEID : PACKED ARRAY [1..8] OF CHAR) :INTEGER;
        EXTERNAL;

The call syntax is:

    RESULT := TREESEARCH (ROOTPTR, NODEPTR, NAMEID);

where ROOTPTR is a pointer to the root node of the tree to be searched, 
NODEPTR is a reference to a pointer variable to be updated by TREESEARCH, and 
NAMEID contains the eight-character name to be searched for in the tree.

The nodes in the binary tree are assumed to be linked records of the type:

NODE = RECORD
              NAME : PACKED ARRAY[1..8] OF CHAR;
              LEFTLINK, RIGHTLINK : ^NODE;

              {other fields can be anything}

       END; 

The actual names of the type and the field identifiers are not important; 
TREESEARCH assumes only that the first eight bytes of the record contain an 
eight-character name and are followed by two pointers to other nodes.

It is also assumed that names are not duplicated within the tree and are 
assigned to nodes according to an alphabetical rule; for a given node, the 
name of the left subnode is alphabetically less than the name of the node, and 
the name of the right subnode is alphabetically greater than the name of the 
node.  Finally, any links that do not point to other nodes should be NIL.

TREESEARCH can return any of three values:

     0    The name passed to TREESEARCH (as the third parameter) has been 
          found in the tree.  The node pointer (second parameter) now points 
          to the node with the specified name.
     1    The name is not in the tree.  If it is added to the tree, it 
          should be the right subnode of the node pointed to by the node 
          pointer.
    -1    The name is not in the tree.  If it is added to the tree, it 
          should be the left subnode of the node pointed to by the node 
          pointer.

The TREESEARCH function does not perform any type checking on the parameters 
passed to it.


The IDSEARCH Procedure

IDSEARCH is a fast assembly language procedure that scans Apple II Pascal 
source text for identifiers and reserved words.  Note that IDSEARCH recognizes 
only identifiers and reserved words--you have to scan for special characters 
and comments yourself.

The external declaration is:

    PROCEDURE IDSEARCH (VAR OFFSET:INTEGER;
                       VARBUFFER:BYTESTREAM);
        EXTERNAL;

The call syntax is:

    IDSEARCH (OFFSET, BUFFER);

To use IDSEARCH, you must include the following declarations in your program.  
Note that the variables (except BUFFER) must be declared in exactly the order 
and types shown.

TYPE 

    {SYMBOL is the enumerated type of symbols in the Apple // Pascal 
language}

    SYMBOL =    (IDENT,COMMA,COLON,SEMICOLON,LPARENT,RPARENT,DOSY,TOSY,
                DOWNTOSY,ENDSY,UNTILSY,OFSY,THENSY,ELSESY,BECOMES,LBRACK,
                RBRACK,ARROW,PERIOD,BEGINSY,IFSY,CASESY,REPEATSY,WHILESY,
                FORSY,WITHSY,GOTOSY,LABELSY,CONSTSY,TYPESY,VARSY,PROCSY,
                FUNCSY,PROGSY,FORWARDSY,INTCONST,REALCONST,STRINGCONST,
                NOTSY,MULOP,ADDOP,RELOP,SETSY,PACKEDSY,ARRAYSY,RECORDSY,
                FILESY,OTHERSY,LONGCONST,USESSY,UNITSY,INTERSY,IMPLESY,
                EXTERNLSY,OTHERWSY); 

    {The reserved words corresponding to the above symbols are as follows - 

    DOSY       - DO       WITHSY      - WITH        RELOP      - IN
    TOSY       - TO       GOTOSY      - GOTO        SETSY      - SET
    DOWNTOSY   - DOWNTO   LABELSY     - LABEL       PACKEDSY   - PACKED 
    ENDSY      - END      CONSTSY     - CONST       ARRAYSY    - ARRAY 
    UNTILSY    - UNTIL    TYPESY      - TYPE        RECORDSY   - RCORD
    OFSY       - OF       VARSY       - VAR         FILESY     - FILE
    THENSY     - THEN     PROCSY      - PROCEDURE   USESSY     - USES
    ELSESY     - ELSE     FUNCSY      - FUNCTION    UNITSY     - UNIT 
    BEGINSY    - BEGIN    PROGSY      - PROGRAM     INTERSY    -.INTERFACE
    IFSY       - IF                     SEGMENT     IMPLESY    -.IMPLEMENTATION
    CASESY     - CASE     FORWARDSY   - FORWARD     EXTERNLSY  - EXTERNAL
    REPEATSY   - REPEAT   NOTSY       - NOT         OTHERWSY   - OTHERWISE
    WHILESY    - WHILE    MULOP       - AND,DIV,MOD
    FORSY      - FOR      ADDOP       - OR          } 

    {OPERATOR expands the multiplicative (MULOP), additive (ADDOP) and
    relational (RELOP) operators}

    OPERATOR =     (MUL,RDIV,ANDOP,IDIV,IMOD,PLUS,MINUS,OROP,LTOP,LEOP,
                   GEOP,GTOP,NEOP,EQOP,INOP,NOOP); 

    ALPHA = PACKED ARRAY [1..8] OF CHAR; 

VAR 
    {the next four variables must be declared in the order shown}
    OFFSET : INTEGER;
    SY : SYMBOL; 
    OP : OPERATOR;
    ID : ALPHA;

IDSEARCH begins by looking for an identifier at the character pointed to by 
BUFFER[OFFSET] and assumes that this character is alphabetic.  IDSEARCH 
produces the following results:

o    BUFFER[OFFSET] points to the character following the identifier 
     just found.
o    ID contains the first eight alphanumeric characters of the 
     identifier just found, left justified and padded with spaces as 
     necessary.
o    SY contains the symbol associated with the identifier just found 
     if the identifier is a reserved word or IDENT if the identifier is 
     not a reserved word.  For example, the identifier MOD translates 
     to MULOP; the identifier ARRAY translates to ARRAYSY, and the 
     identifier MYLABEL translates to IDENT.
o    OP contains the operator value which corresponds to the identifier 
     just found if the identifier is an operator, or NOOP if the 
     identifier is not an operator.  For example, the identifier MOD 
     translates to IMOD, the identifier ARRAY translates to NOOP, and 
     the identifier MYLABEL translates to NOOP.

The following is an example of calling IDSEARCH:

    BEGIN
        IF BUFFER[OFFSET] IN ['A'..'Z','a'..'z'] THEN
            IDSEARCH (OFFSET, BUFFER);     
    END;

The following is an algorithmic representation of IDSEARCH:

    PROCEDURE IDSEARCH (VAR OFFSET:INTEGER; VAR BUFFER:BYTESTREAM);
    BEGIN 
        ID := ScanIdentifier (OFFSET, BUFFER);
        SY := LookUpReservedWord (ID); 
        OP := LookUpOperator (ID);
    END;

ScanIdentifier increments OFFSET until BUFFER[OFFSET] is no longer part of an 
identifier, copying the first eight alphanumeric characters passed into ID 
(left justified, padding with spaces).

LookUpReservedWord translates an identifier into the associated symbol 
(defaulting to IDENT).

LookUpOperator translates an identifier into the associated operator 
(defaulting to NOOP).



